package tree;

import java.util.*;

// 遍历二叉树
public class TraversalBinaryTree {

    private static List<Integer> result = new ArrayList<>();

    public static void main(String[] args) {

        // 手动构造一棵二叉树
        TreeNode root = CreateTree.createBinaryTree2();

        // 递归形式的前、中、后序遍历
        recurision(root);

        // 非递归形式(迭代)遍历二叉树[本质上是在模拟递归，因为在递归的过程中使用了系统栈，所以在迭代的解法中常用Stack来模拟系统栈。]
        // iteration(root);

        // 层次遍历二叉树(使用队列)
        // TreeNode root1 = CreateTree.createBinaryTree2();
        // List<List<Integer>> result = levelOrder(root1);
        // System.out.println("层序遍历二叉树" + result);
    }

    private static List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null){
            return result;
        }
        // 创建队列
        Queue<TreeNode> queue = new LinkedList<>();
        // 根节点入队列
        queue.add(root);
        while (!queue.isEmpty()){
            // 得到当前队列中节点的个数(也就是二叉树节点的个数)
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while (count > 0){
                TreeNode tempNode = queue.poll();
                list.add(tempNode.getValue());
                if(tempNode.getLeft() != null){
                    queue.add(tempNode.getLeft());
                }
                if(tempNode.getRight() != null){
                    queue.add(tempNode.getRight());
                }
                count--;
            }
            result.add(list);
        }
        return result;
    }

    ///////////////////////////////////// 迭代遍历二叉树 begin//////////////////////////////////
    private static void iteration(TreeNode root) {

        // 前序(迭代)遍历二叉树
        result.clear();
        List<Integer> preOrderIterationResult = preOrderIteration(root);
        System.out.println("前序(迭代)遍历二叉树(根左右)" + preOrderIterationResult);

        // 中序(迭代)遍历二叉树
        result.clear();
        List<Integer> inOrderIterationResult = inOrderIteration(root);
        System.out.println("中序(迭代)遍历二叉树(左根右)" + inOrderIterationResult);

        // 后序(迭代)遍历二叉树
        result.clear();
        List<Integer> postOrderIterationResult = postOrderIteration(root);
        System.out.println("后序(迭代)遍历二叉树(左右根)" + postOrderIterationResult);

    }

    // 后序(迭代)遍历二叉树
    private static List<Integer> postOrderIteration(TreeNode root){
        if(root == null){
            return result;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        stack1.push(root);
        while (!stack1.isEmpty()){
            TreeNode node = stack1.pop();
            stack2.push(node);
            if(node.getLeft() != null){
                stack1.push(node.getLeft());
            }
            if(node.getRight() != null){
                stack1.push(node.getRight());
            }
        }
        while (!stack2.isEmpty()){
            result.add(stack2.pop().getValue());
        }
        return result;
    }

    // 中序(迭代)遍历二叉树
    private static List<Integer> inOrderIteration(TreeNode root) {
        if(root == null){
            return result;
        }
        TreeNode cur = root;
        Stack<TreeNode> stack = new Stack<>();
        while (!stack.isEmpty() || cur != null){
            while (cur != null){
                stack.push(cur);
                cur = cur.getLeft();
            }
            TreeNode node = stack.pop();
            result.add(node.getValue());
            if(node.getRight() != null){
                cur = node.getRight();
            }
        }
        return result;
    }

    // 前序(迭代)遍历二叉树
    private static List<Integer> preOrderIteration(TreeNode root) {
        if(root != null){
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()){
                TreeNode node = stack.pop();
                result.add(node.getValue());
                if(node.getRight() != null){
                    stack.push(node.getRight());
                }
                if(node.getLeft() != null){
                    stack.push(node.getLeft());
                }
            }
        }
        return result;
    }
    ///////////////////////////////////// 迭代遍历二叉树 end //////////////////////////////////



    ///////////////////////////////////// 递归遍历二叉树 begin//////////////////////////////////
    private static void recurision(TreeNode root) {
        // 前序遍历二叉树
        result.clear();
        List<Integer> preOrderResult = preOrderTraverse(root);
        System.out.println("前序遍历二叉树(根左右)" + preOrderResult);

        // 中序遍历二叉树
        result.clear();
        List<Integer> inOrderResult = inOrderTraverse(root);
        System.out.println("中序遍历二叉树(左根右)" + inOrderResult);

        // 后序遍历二叉树
        result.clear();
        List<Integer> postOrderResult = postOrderTraverse(root);
        System.out.println("后序遍历二叉树(左右根)" + inOrderResult);
    }

    // 后序遍历二叉树
    private static List<Integer> postOrderTraverse(TreeNode root) {
        if(root != null){
            postOrderTraverse(root.getLeft());
            postOrderTraverse(root.getRight());
            result.add(root.getValue());
        }
        return result;
    }

    // 中序遍历二叉树
    private static List<Integer> inOrderTraverse(TreeNode root) {
        if(root != null){
            inOrderTraverse(root.getLeft());
            result.add(root.getValue());
            inOrderTraverse(root.getRight());
        }
        return result;
    }

    // 前序遍历二叉树
    private static List<Integer> preOrderTraverse(TreeNode root) {
        if (root != null) {
            result.add(root.getValue());
            preOrderTraverse(root.getLeft());
            preOrderTraverse(root.getRight());
        }
        return result;
    }

    // 前序遍历二叉树
    public static List<Integer> preOrderTraverse_2(TreeNode root) {
        // 这个存放结果的List集合一定不能写在递归里面
        //List<Integer> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        result.add(root.getValue());
        preOrderTraverse_2(root.getLeft());
        preOrderTraverse_2(root.getRight());
        return result;
    }
    ///////////////////////////////////// 递归遍历二叉树 end //////////////////////////////////


}
